
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        queue = [root]
        while queue:
            pre = None
            new_queue = []
            for i in range(len(queue)):
                if pre:
                    root.next = pre
                pre = queue[i]
                if root.left:
                    new_queue.append(queue[i].left)
                    new_queue.append(queue[i].right)
            queue = new_queue
        return root

# 看了官方的题解还有一种解法，感觉挺有意思，也写一遍
# 主要利用了，先建立的链表关系， head.right.next = head.next.left,来链接
# 具体可以看题解 https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        tree = root 
        while tree.left:
            head = tree

            while head:

                head.left.next = head.right
                if head.next:
                    head.right.next = head.next.left
                head = head.next

            tree = tree.left
        return root
